import java.util.ArrayList;
import java.util.LinkedList;

public class NFA {

	// First dimension: States
	// Second dimension: Inputs
	// Third dimension: Destination state
	ArrayList<State> table;

	String name;

	State start = null;

	State accept = null;

	static final int NUM_CHAR = 256;

	private NFA(String name) {// Returns empty NFA

		table = new ArrayList<State>();
		this.name = name;
	}

	public boolean isEmpty() {
		if (start == null)
			return true;
		return false;
	}

	public NFA(String name, int startIndex, int endIndex, char c) {// Returns
																	// simple
																	// NFA with
																	// transfers
																	// from
																	// start
																	// index to
																	// end
																	// index. If
																	// c is '+',
																	// it will
																	// return
																	// (NFA)+,
																	// if c is
																	// '*', it
																	// will
																	// return
																	// (NFA)*
		table = new ArrayList<State>();
		this.name = name;
		State s1 = addState(new State());
		State s2 = addState(new State());

		if (c == '*') {
			State s3 = addState(new State());
			State s4 = addState(new State());
			addTransition(0, 0, s1, s3);
			addTransition(0, 0, s1, s2);
			addTransition(startIndex, endIndex, s3, s4);
			addTransition(0, 0, s4, s3);
			addTransition(0, 0, s4, s2);
		} else if (c == '+') {
			addTransition(startIndex, endIndex, s1, s2);
			addTransition(startIndex, endIndex, s2, s2);
		} else {
			addTransition(startIndex, endIndex, s1, s2);
		}

		start = s1;
		accept = s2;
	}

	public NFA(String name, int startIndex, int endIndex, char c, NFA n,
			boolean not) {// returns an NFA where it tests each character
							// against the rule before adding it. If 'not' is
							// true, it will add characters in the rule, but not
							// between the characters. If rule is null, it will
							// not test it against a rule
		table = new ArrayList<State>();
		this.name = name;
		State s1 = addState(new State());
		State s2 = addState(new State());

		Rule r = new Rule(n);

		if (!not) {
			if (c == '*') {
				State s3 = addState(new State());
				State s4 = addState(new State());
				addTransition(0, 0, s1, s3, r);
				addTransition(0, 0, s1, s2, r);
				addTransition(startIndex, endIndex, s3, s4, r);
				addTransition(0, 0, s4, s3, r);
				addTransition(0, 0, s4, s2, r);
			} else if (c == '+') {
				addTransition(startIndex, endIndex, s1, s2, r);
				addTransition(startIndex, endIndex, s2, s2, r);
			} else {
				addTransition(startIndex, endIndex, s1, s2, r);
			}
		} else {
			if (c == '*') {
				State s3 = addState(new State());
				State s4 = addState(new State());
				addTransition(0, 0, s1, s3, r);
				addTransition(0, 0, s1, s2, r);
				addTransition(1, startIndex-1, s3, s4, r);
				addTransition(endIndex+1, NUM_CHAR - 1, s3, s4, r);
				addTransition(0, 0, s4, s3, r);
				addTransition(0, 0, s4, s2, r);
			} else if (c == '+') {
				addTransition(1, startIndex-1, s1, s2, r);
				addTransition(endIndex+1, NUM_CHAR - 1, s1, s2, r);
				addTransition(0, 0, s2, s1, r);
			} else {
				addTransition(1, startIndex-1, s1, s2, r);
				addTransition(endIndex+1, NUM_CHAR - 1, s1, s2, r);

			}
		}

		start = s1;
		accept = s2;
	}

	public NFA(String name, int startIndex, int endIndex, char c, Rule r,
			boolean not) {// returns an NFA where it tests each character
							// against the rule before adding it. If 'not' is
							// true, it will add characters in the rule, but not
							// between the characters. If rule is null, it will
							// not test it against a rule
		table = new ArrayList<State>();
		this.name = name;
		State s1 = addState(new State());
		State s2 = addState(new State());

		if (!not) {
			if (c == '*') {
				State s3 = addState(new State());
				State s4 = addState(new State());
				addTransition(0, 0, s1, s3, r);
				addTransition(0, 0, s1, s2, r);
				addTransition(startIndex, endIndex, s3, s4, r);
				addTransition(0, 0, s4, s3, r);
				addTransition(0, 0, s4, s2, r);
			} else if (c == '+') {
				addTransition(startIndex, endIndex, s1, s2, r);
				addTransition(startIndex, endIndex, s2, s2, r);
			} else {
				addTransition(startIndex, endIndex, s1, s2, r);
			}
		} else {
			if (c == '*') {
				State s3 = addState(new State());
				State s4 = addState(new State());
				addTransition(0, 0, s1, s3, r);
				addTransition(0, 0, s1, s2, r);
				addTransition(1, startIndex-1, s3, s4, r);
				addTransition(endIndex+1, NUM_CHAR - 1, s3, s4, r);
				addTransition(0, 0, s4, s3, r);
				addTransition(0, 0, s4, s2, r);
			} else if (c == '+') {
				addTransition(1, startIndex-1, s1, s2, r);
				addTransition(endIndex+1, NUM_CHAR - 1, s1, s2, r);
				addTransition(0, 0, s2, s1, r);
			} else {
				addTransition(1, startIndex-1, s1, s2, r);
				addTransition(endIndex+1, NUM_CHAR - 1, s1, s2, r);

			}
		}

		start = s1;
		accept = s2;
	}

	public State getStart() {

		return start;
	}

	public State addState(State state) {

		if (table.isEmpty()) {
			start = state;
		}

		table.add(state);

		return state;
	}

	public void fixAccepting() {

		for (int i = 0; i < table.size(); i++) {
			table.get(i).setAccepting(false);
		}
		accept.setAccepting(true);
	}
/*
	public void addTransition(int startIndex, int endIndex,
			State destinationState) {

		ArrayList<State> d = new ArrayList<State>(1);
		d.set(0, destinationState);
		addTransition(startIndex, endIndex, d, table.size() - 1);
	}
*/
	public void addTransition(int startIndex, int endIndex,
			ArrayList<State> destinationStates) {
		addTransition(startIndex, endIndex, destinationStates, table.size() - 1);
	}

	public void addTransition(int startIndex, int endIndex,
			ArrayList<State> destinationStates, int id) {
		table.get(id).addTransition(startIndex, endIndex, destinationStates);
	}

	public void addTransition(int startIndex, int endIndex, State startState,
			State endState) {
		startState.addTransition(startIndex, endIndex, endState);

	}

	public void addTransition(int startIndex, int endIndex, State startState,
			State endState, Rule r) {
		startState.addTransition(startIndex, endIndex, endState, r);

	}

	public void removeTransition(int startIndex, int endIndex,
			State startState, State endState) {
		startState.removeTransition(startIndex, endIndex, endState);
	}

	public int getSize() {
		return table.size();
	}

	public boolean match(String s) {
		return matchHelper(s, start);
	}

	private boolean matchHelper(String s, State curr) {

		ArrayList<State> empty = curr.getNext(0);

		if (s.isEmpty()) {// End of string
			boolean m = curr.getId() == accept.getId();

			for (int i = 0; i < empty.size(); i++) {
				m = m || matchHelper(s, empty.get(i));
				if (m) {
					return m;
				}
			}

			return m;
		}
		ArrayList<State> next = curr.getNext(s.charAt(0));

		if (next.isEmpty() && empty.isEmpty()) {// Nowhere to go with next
												// character
			return false;
		} else if (s.length() == 1) {
			boolean m = false;
			for (int i = 0; i < next.size(); i++) {
				m = m || matchHelper("", next.get(i));
				if (m) {
					return m;
				}
			}
			for (int i = 0; i < empty.size(); i++) {
				m = m || matchHelper(s, empty.get(i));
				if (m) {
					return m;
				}
			}

			return m;
		} else {

			boolean m = false;
			for (int i = 0; i < next.size(); i++) {
				m = m || matchHelper(s.substring(1, s.length()), next.get(i));
				if (m) {
					return m;
				}
			}
			for (int i = 0; i < empty.size(); i++) {
				m = m || matchHelper(s, empty.get(i));
				if (m) {
					return m;
				}
			}

			return m;
		}

	}

	/*
	 * public void increment(int n){ for(int i=0; i<table.size(); i++){
	 * table.get(i).setId(table.get(i).getId()+n); }
	 * 
	 * }
	 */
	/*
	 * public void union(NFA n){
	 * 
	 * int s = getSize();
	 * 
	 * n.increment(s);
	 * 
	 * table.addAll(n.table);
	 * 
	 * State k = addEmptyState();
	 * 
	 * 
	 * addTransition(0,0,getState(0)); addTransition(0,0,n.getState(0));
	 * 
	 * start = k;
	 * 
	 * }
	 */
	public State getState(int id) {
		return table.get(id);
	}

	public static NFA emptyNFA() {
		return new NFA("empty", 0, 0, ' ');
	}

	public static NFA blankNFA() {
		NFA n1 = new NFA("blank");
		State s1 = n1.addState(new State());
		State s2 = n1.addState(new State());
		n1.start = s1;
		n1.accept = s2;
		return n1;
	}

	public NFA cloneNFA() {
		return cloneNFA(name);

	}

	public NFA cloneNFA(boolean print) {
		return cloneNFA(name, print);
	}

	public NFA cloneNFA(String newName) {
		return cloneNFA(newName, false);
	}

	public NFA cloneNFA(String newName, boolean print) { // clones and prints an
															// NFA
		LinkedList<State> s = new LinkedList<State>();
		LinkedList<State> n = new LinkedList<State>();

		LinkedList<State> visited = new LinkedList<State>();
		LinkedList<State> newVisited = new LinkedList<State>();

		s.add(start);
		State curr;
		State newStart = new State();
		State copy;
		State k;
		n.add(newStart);

		NFA c = new NFA(name);
		c.start = newStart;
		if (print)
			System.out.println("Cloning NFA  \"" + name + "\"");
		while (!s.isEmpty()) {
			while (!s.isEmpty()) {
				curr = s.getFirst();
				copy = n.getFirst();

				if(print)System.out.println("Info for state "+curr.getId());
				
				for (int i = 0; i < NUM_CHAR; i++) {
					for (int j = 0; j < curr.next.get(i).size(); j++) {
						if (print) {
							System.out.print("Transition from " + curr.getId()
									+ " to " + curr.next.get(i).get(j).getId()
									+ " on character " + (char)i);
							if (curr.next.get(i).get(j) == accept) {
								System.out.print(" Accept state\n");
							} else {
								System.out.print("\n");
							}

						}
						int a = s.indexOf((State) curr.next.get(i).get(j));
						int b = visited
								.indexOf((State) curr.next.get(i).get(j));

						if (a != -1) {// state already in queue

							k = n.get(a);
							copy.addTransition(i, i, k);

						} else if (b != -1) {// state already in visited nodes

							k = newVisited.get(b);
							copy.addTransition(i, i, k);
						} else {
							s.add(curr.next.get(i).get(j));
							k = new State();
							n.add(k);
							if (curr.next.get(i).get(j) == accept) {
								c.accept = k;
							}

							copy.addTransition(i, i, k);
						}
					}
				}

				s.pop();
				c.addState(n.pop());
				visited.add(curr);
				newVisited.add(copy);
			}
			for(int z=0; z<table.size(); z++){
				if(!visited.contains(table.get(z))){
					s.add(table.get(z));
					n.add(new State());
					z+=table.size();
				}
			}
		}
		if (print)
			System.out.println();
		changeName(newName);
		return c;

	}

	public void changeName(String s) {

		name = s;

		for (int i = 0; i < table.size(); i++) {
			table.get(i).setName(s);
		}

	}

	public void union(NFA n) {// Changes NFA "whatever" into "(whatever)|(n)"
		State s1 = addState(new State());
		
		addTransition(0,0, s1,start);
		addTransition(0,0, s1,n.start);
		
		start = s1;
		
		
		accept.copyTransitionsFrom(n.accept);
		
		n.accept.addTransition(0, 0, accept);
		combineTables(n);
		changeName(name +"|"+ n.name);

	}
	
	private void combineTables(NFA n){
		table.addAll(n.table);
	}

	public void concat(NFA n) {// Changes NFA "whatever" into "(whatever)(n)"

		accept.copyTransitionsFrom(n.start);
		accept = n.accept;
		combineTables(n);
		changeName(name + n.name);

	}

	public void frontcat(NFA n) {
		n.concat(this);
		start = n.start;
	}

	public void star() {// Changes NFA "whatever" into "(whatever)*"
		State s1 = addState(new State());
		State s2 = addState(new State());

		addTransition(0, 0, s1, start);
		addTransition(0, 0, s1, s2);
		addTransition(0, 0, accept, start);
		addTransition(0, 0, accept, s2);

		start = s1;
		accept = s2;
		changeName(name+"*");
	}

	public void plus() { // Changes NFA "whatever" into "(whatever)+"
		addTransition(0, 0, accept, start);
		changeName(name+"+");
	}

	public static ArrayList<State> emptyClosure(State s) {
		ArrayList<State> result = new ArrayList<State>();

		ArrayList<State> curr;

		result.add(s);

		boolean b = true;

		while (b) {
			b = false;
			for (int i = 0; i < result.size(); i++) {
				curr = result.get(i).getNext(0);
				for (int j = 0; j < curr.size(); j++) {
					if (!result.contains(curr.get(j))) {
						result.add(curr.get(j));

						b = true;
					}
				}
			}
		}

		return result;
	}

	public static ArrayList<State> emptyClosure(ArrayList<State> s) {
		ArrayList<State> result = new ArrayList<State>();

		ArrayList<State> curr;

		result.addAll(s);

		boolean b = true;

		while (b) {
			b = false;
			for (int i = 0; i < result.size(); i++) {
				curr = result.get(i).getNext(0);
				for (int j = 0; j < curr.size(); j++) {
					if (!result.contains(curr.get(j))) {
						result.add(curr.get(j));
						b = true;
					}
				}
			}
		}

		return result;

	}

	public static ArrayList<State> moveFunction(ArrayList<State> s, int c) {

		ArrayList<State> result = new ArrayList<State>();

		ArrayList<State> curr;

		for (int i = 0; i < s.size(); i++) {
			curr = s.get(i).getNext(c);

			for (int j = 0; j < curr.size(); j++) {

				if (!result.contains(curr.get(j))) {
					result.add(curr.get(j));
				}
			}
		}

		boolean b = true;

		while (b) {
			b = false;
			for (int i = 0; i < result.size(); i++) {
				curr = result.get(i).getNext(c);
				for (int j = 0; j < curr.size(); j++) {
					if (!result.contains(curr.get(j))) {
						result.add(curr.get(j));
						b = true;
					}
				}
			}
		}

		return result;

	}

}
